package arithmetic.demo24;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

/**
 * 动态规划： 完全背包 + 累加个数：零钱兑换(II)
 */
class Solution {
    public int change(int amount, int[] coins) {
        // 动态规划 + 完全背包
        int len = coins.length;

        // 创建dp
        int[][] dp = new int[len+1][amount+1];
        // 初始化
        dp[0][0] = 1;


        //填表
        for(int i = 1; i <= len; i++) {
            for(int j = 0; j <= amount; j++) {
                // 先继承前面的
                dp[i][j] = dp[i-1][j];
                int index  = j - coins[i-1];
                if(index >= 0 ) {
                    dp[i][j] += dp[i][index];
                }
            }
        }

        return dp[len][amount];
    }
}

/**
 * 动态规划：  完全背包 + 累加个数：零钱兑换
 */

class Solution1 {
    public int coinChange(int[] coins, int amount) {
        // 动态规划 + 完全背包
        int len = coins.length;
        int INF = 0x3f3f3f3f;

        // 特判一下
        if (amount == 0) {
            return 0;
        }

        // 创建dp
        int[][] dp = new int[len+1][amount+1];

        // 初始化
        for(int j = 1; j <= amount; j++) {
            dp[0][j] = INF;
        }

        //填表
        for(int i = 1; i <= len; i++) {
            for(int j = 0; j <= amount; j++) {
                // 先继承前面的
                dp[i][j] = dp[i-1][j];
                int index  = j - coins[i-1];
                if(index >= 0 && dp[i][index] != INF) {
                    dp[i][j] = Math.min(dp[i][j] ,dp[i][index] + 1);
                }
            }
        }

        return dp[len][amount] == INF ? -1 : dp[len][amount];
    }
}

/**
 *  动态规划：  完全背包 + 累加个数：零钱兑换(优化版)
 */

class Solution2 {
    public int coinChange(int[] coins, int amount) {
        // 动态规划 + 完全背包
        int len = coins.length;
        int INF = 0x3f3f3f3f;

        // 特判一下
        if (amount == 0) {
            return 0;
        }

        // 创建dp
        int[] dp = new int[amount+1];

        // 初始化
        for(int j = 1; j <= amount; j++) {
            dp[j] = INF;
        }

        //填表
        for(int i = 1; i <= len; i++) {
            for(int j = coins[i-1]; j <= amount; j++) {
                // 先继承前面的
                int index  = j - coins[i-1];
                if(index >= 0 && dp[index] != INF) {
                    dp[j] = Math.min(dp[j] ,dp[index] + 1);
                }
            }
        }

        return dp[amount] == INF ? -1 : dp[amount];
    }
}


/**
 * 动态规划： 完全背包 + 累加个数：零钱兑换(II)(优化版)
 */

class Solution3 {
    public int change(int amount, int[] coins) {
        // 动态规划 + 完全背包
        int len = coins.length;

        // 创建dp
        int[] dp = new int[amount+1];
        // 初始化
        dp[0] = 1;


        //填表
        for(int i = 1; i <= len; i++) {
            for(int j = coins[i-1]; j <= amount; j++) {
                // 先继承前面的
                int index  = j - coins[i-1];
                if(index >= 0 ) {
                    dp[j] += dp[index];
                }
            }
        }

        return dp[amount];
    }
}


/**
 * 动态规划: 完全背包 + 最小个数 ： 完全平方数
 */

class Solution4 {
    public int numSquares(int n) {
        // 动态规划+ 完全背包

        // 定义 Integer 的最大值
        int INF = 0x3f3f3f3f;
        int len = (int)Math.sqrt(n);

        // 创建dp
        int[][] dp = new int[len+1][n + 1];

        // 初始化
        for(int j = 1; j <= n; j++) {
            dp[0][j] = INF;
        }

        // 状态转移
        for(int i = 1; i <= len; i++) {
            for(int j = 0 ; j <= n; j++) {
                // 先继承前面的长度
                dp[i][j] = dp[i-1][j];
                int index = j - i * i;
                if(index >= 0 && dp[i][index] != INF) {
                    dp[i][j] = Math.min(dp[i][j] , dp[i][index] + 1);
                }
            }
        }

        // 确定返回值
        return  dp[len][n] == INF ? 1 : dp[len][n];
    }
}
class Test {
    public static void main(String[] args) {
        Solution4 solution4 = new Solution4();
        System.out.println(solution4.numSquares(12));
    }
}

/**
 * 动态规划: 完全背包 + 最小个数 ： 完全平方数(优化版)
 */


class Solution5 {
    public int numSquares(int n) {
        // 动态规划+ 完全背包

        // 定义 Integer 的最大值
        int INF = 0x3f3f3f3f;
        int len = (int)Math.sqrt(n);

        // 创建dp
        int[] dp = new int[n + 1];

        // 初始化
        for(int j = 1; j <= n; j++) {
            dp[j] = INF;
        }

        // 状态转移
        for(int i = 1; i <= len; i++) {
            for(int j = i * i ; j <= n; j++) {

                int index = j - i * i;
                if(index >= 0 && dp[index] != INF) {
                    dp[j] = Math.min(dp[j] , dp[index] + 1);
                }
            }
        }

        // 确定返回值
        return  dp[n] == INF ? 1 : dp[n];
    }
}


/**
 * 动态规划： 完全背包（优化版）
 */

// 注意类名必须为 Main, 不要有任何 package xxx 信息
 class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int len = in.nextInt(), maxV = in.nextInt();
        int[] V = new int[len + 1], W = new int[len + 1];

        // 输入
        for (int i  = 1 ; i <= len; i++ ) {
            V[i] = in.nextInt();
            W[i] = in.nextInt();
        }

        // 创建dp
        int[] dp = new int[maxV + 1];

        for (int i = 1; i <= len; i++) {
            for (int j = V[i]; j <= maxV; j++) {
                // 开始判断当前要的情况
                dp[j] = Math.max(dp[j], dp[j - V[i]] + W[i]);

            }
        }

        System.out.println(dp[maxV]);



        // 创建dp
        dp = new int[maxV + 1];

        // 初始化
        for (int j  = 1 ; j <= maxV; j++) {
            dp[j] = -1;
        }

        for (int i = 1; i <= len; i++) {
            for (int j = V[i]; j <= maxV; j++) {


                // 开始判断当前要的情况
                int index = j - V[i];
                if (dp[index] != -1) {
                    dp[j] = Math.max(dp[j], dp[index] + W[i]);
                }

            }
        }

        System.out.println(dp[maxV] == -1 ? 0 : dp[maxV]);

    }
}
